The present invention relates generally to instruction processing, and more specifically, to variable updates of branch prediction states when processing branch instructions.
Branch prediction is a performance-critical component of a pipelined high-frequency microprocessor. It is used to predict the direction (“taken” vs. “not-taken”) and the target address of each branch instruction. This is beneficial because it allows processing to continue along a branch's predicted path rather than having to wait for the outcome of the branch to be determined. A penalty is incurred only if a branch is mis-predicted.
A branch target buffer (BTB) is a structure that stores branch and target information. It is a cache of branch information and in many ways is analogous to instruction and data caches. Lee and Smith, “Branch Prediction Strategies and Branch Target Buffer Design,” Computer, January 1984, describes branch target buffers, and this document is incorporated by reference herein in its entirety. U.S. Pat. No. 5,574,871, “Method and Apparatus for Implementing a Set-Associative Branch Target Buffer,” filed Jan. 4, 1994, which patent is incorporated herein by reference, describes a BTB circuit in a computer processor that predicts branch instructions with a stream of computer instructions. The BTB circuit uses a BTB cache that stores branch information about previously executed branch instructions. The branch information stored in the BTB cache is addressed by the last byte of each branch instruction. When an instruction fetch unit in the computer processor fetches a block of instructions it sends the BTB circuit an instruction pointer. Based on the instruction pointer, the BTB circuit looks in the BTB cache to see if any of the instructions in the block being fetched is a branch instruction. When the BTB circuit finds an upcoming branch instruction in the BTB cache, the BTB circuit informs an instruction fetch unit about the upcoming branch instruction.
Other structures, such as a Branch History Table (BHT), a Pattern History Table (PHT), and a Multiple Target Table (MTT), can be included to store additional information used for branch direction and target prediction. For example, U.S. Pat. No. 7,082,520, “Branch Prediction Utilizing Both a Branch Target Buffer and a Multiple Target Table”, filed May 9, 2002, which is incorporated herein by reference, describes an improved branch prediction process that utilizes both a BTB and a MTT for providing the capability to predict multiple targets for a single branch. A MTT when used in conjunction with a BTB allows for branches which have changing targets to be able to selectively choose the target of choice based on the execution path that was taken that lead to the given branch. The method predicts target addresses, and between the static and dynamic target address, and upon finding a hit, the target is sent to the instruction cache such that a fetch can begin for the current target address and the target address is sent back to the BTB to begin the search for the next branch given the current target predicted address. Upon resolving a branch the dynamic target is placed in MTT for future use.
A BHT or a PHT usually uses saturating counters as a state machine to predict the direction of branches. A BHT is indexed based on the instruction address of the branch itself. A PHT is indexed based on the path taken to get to the branch. Usually, each table entry is a two-bit saturating counter, but other sizes are also possible. The saturating counter attempts to learn the dominant behavior of a branch or multiple branches mapping to the same table entry, and the saturating counter predicts that direction.
Sometimes the branches that map to a BHT or PHT entry exhibit a pattern that is difficult to predict. For example, a pattern that alternates between “not taken” and “taken” may be difficult to predict and the accuracy of the prediction may vary based upon an initial state when the pattern begins.